package com.cat.chapter046;

import java.util.HashMap;

/**
 * @author cat
 * @description https://leetcode.cn/problems/make-sum-divisible-by-p/
 * @create 2025/7/15 17:50
 * @since JDK17
 */

public class Solution05 {
    static HashMap<Integer, Integer> map = new HashMap<>();

    public int minSubarray(int[] nums, int p) {
        map.clear();
        int sum = 0, ans = Integer.MAX_VALUE, cur = 0;
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            sum = (sum + nums[i]) % p;
            map.put(sum, i);
        }

        for (int i = 0; i < nums.length; i++) {
            cur = (cur + nums[i]) % p;  // 当前的余数
            int want = cur >= sum ? cur - sum : cur + p - sum;  // 目标
            if (map.containsKey(want)) {
                ans = Math.max(ans, i - map.get(want));
            }
            map.put(cur, i);
        }
        return ans;
    }
}